package problems.contest;

import java.util.PriorityQueue;

/**
 * 第 342 场周赛
 * <p>https://leetcode.cn/contest/weekly-contest-342</p>
 *
 * @author dubulingbo, 2023-04-23, 023 10:27.
 */
public class WCT342 {
    /**
     * T1
     */
    public int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
        return (arrivalTime + delayedTime) % 24;
    }

    /**
     * T2
     */
    public int sumOfMultiples(int n) {
        int sum = 0;

        for (int i = 3; i <= n; ++i) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }

        return sum;
    }

    /**
     * T3
     */
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;

        int[] heap = new int[101];
        int[] arr = new int[n - k + 1];
        for (int i = 0; i < n; ++i) {
            ++heap[nums[i] + 50];
            if (i >= k - 1) {
                // 获取 heap 中第 x 小的数
                int xth = smallXth(heap, x);
                arr[i - k + 1] = Math.min(xth, 0);
                --heap[nums[i - k + 1] + 50];
            }
        }

        return arr;
    }

    private int smallXth(int[] cnt, int x) {
        int sum = 0;
        for (int i = 0; i < cnt.length; ++i) {
            sum += cnt[i];
            if (sum < x) continue;
            return i - 50;
        }
        return 0;
    }


    /**
     * T4.
     * <p></p>
     */
    public int minOperations(int[] nums) {
        /**
         * 最短gcd=1的子数组
         */
        int n = nums.length;
        int g = 0;
        int oneCnt = 0;

        for (int num : nums) {
            g = gcd(g, num);
            if (num == 1) ++oneCnt;
        }

        if (g > 1) return -1;
        if (oneCnt > 0) return n - oneCnt;

        int minLen = n;
        for (int i = 0; i < n; ++i) {
            g = 0;
            for (int j = i; j < n; ++j) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    minLen = Math.min(minLen, j - i + 1);
                }
            }
        }

        return n + minLen - 2;
    }

    private int gcd(int a, int b) {
        while (b > 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}
